package Algorithm.binarysearchNoRecursion;

public class BinarySearchNoRecursion {
	public static void main(String[] args) {
		int[] array = {4, 5, 9, 9, 12, 13, 14, 15, 15, 18};
		int index = binarySearch(array, 10);
//        int index = binarySearchRecursion(array,0,array.length-1,10,-1);
		System.out.println("index = " + index);
	}


	/**
	 * 二分查找的非递归实现,默认 Array 为升序排列
	 *
	 * @param array  带查找的数组
	 * @param target 目标数
	 * @return 返回目标数的下标，-1 表示没有找到
	 */
	public static int binarySearch(int[] array, int target) {
		int left = 0;
		int right = array.length - 1;
		int lastMid = -1;
		while (left <= right) {//表示可以继续查找
			//大于最大的数，小于最小的数，退出
			if (left > right || target < array[0] || target > array[array.length - 1]) {
				return -1;
			}

			//插值排序，自适应的 mid ，提高查找效率
			int mid = left + (right - left) * (target - array[left]) / (array[right] - array[left]);
			if (array[mid] == target) {
				return mid;
			} else if (lastMid == mid) {
				return -1;
			} else if (array[mid] > target) {
				right = mid - 1;//需要向做查找
				lastMid = mid;
			} else {
				left = mid + 1;
				lastMid = mid;
			}
		}
		return -1;
	}

	//递归形式
	public static int binarySearchRecursion(int[] array, int left, int right, int target, int lastMid) {
		while (left <= right) {
			//大于最大的数，小于最小的数，退出
			if (left > right || target < array[0] || target > array[array.length - 1]) {
				return -1;
			}

			//插值排序，自适应的 mid ，提高查找效率
			int mid = left + (right - left) * (target - array[left]) / (array[right] - array[left]);
			if (array[mid] == target) {
				while (mid - 1 >= 0 && array[mid - 1] == target) {
					mid--;
				}
				return mid;
			} else if (lastMid == mid) {
				return -1;
			} else if (array[mid] > target) {
				return binarySearchRecursion(array, left, mid - 1, target, mid);
			} else {
				return binarySearchRecursion(array, mid + 1, right, target, mid);
			}
		}
		return -1;
	}
}
